The present invention relates generally to generation of logic for a finite state machine (FSM). More particularly, the invention concerns a method for reducing logic in a finite state machine by resolving "don't care" output values when generating logic for the finite state machine (FSM)
In many situations a finite state machine can be represented using standard building blocks, particularly, a next state decode block, state memory storage elements and an output decode block. Typically, the state memory storage elements are delay (D) flip-flops. The D flip-flops store an encoded value which indicates the current state of the finite state machine. The output decode block generates the FSM outputs based on the current state as determined from the encode value stored by the D flip-flops. Combinatorial logic in the next state decode block and the output decode block are reduced to limit the circuitry necessary to implement the finite state machine.
One problem with finite state machines with a structure which utilizes a next state decode block, state memory storage elements and an output decode block is that the outputs to the finite state machine may glitch as the outputs from the state memory storage elements propagate through the output decoder. To eliminate this problem, some designers opt for an alternate architecture which eliminates the output decode logic. In this case, the structure includes only the next state decode block and memory storage elements. The memory storage elements include a dedicated flip-flop for each FSM output. This eliminates the need for the output decode block.
In one variation of finite state machines without output decode blocks there are storage elements for each individual FSM output and, in addition, storage elements which encode the state. In this case the values of the storage elements for the individual FSM outputs are not fed back into the next state decode block to determine the current state.
In another variation of finite state machines without output decode blocks, there are storage elements for each individual FSM output, but there is not storage elements which encode the state. This type of finite state machine may be referred to as an output encoded finite state machine. The state of the output encoded finite state machine is determined by the next state decode block using the value of the FSM outputs. If each state has a unique combination of the values of the FSM outputs, the next state decode block is able to determine the current state using only the FSM outputs. When more than one state has the same combination of the values of the FSM outputs, the next state decode block is no longer able to determine the current state using only the FSM outputs. Therefore, one or more additional storage elements are added and assigned values so that each state has a unique combination of the values stored by all the storage elements, that is a combination of the values of both the FSM outputs and the outputs of the additional storage elements.